2588. Symmetry
Farmer John loves
symmetry and is currently placing cows on his field, which is a rectangular
grid of size n × m.
To preserve
symmetry, Farmer John proceeds as follows. First, he places a cow in the
central cell of the field. If such a cell does not exist, he stops the process.
Then he divides the field into four rectangular subfields of equal size,
separated by the row and the column passing through the central cell containing
the cow. After that, he independently applies the same procedure to each of the
resulting subfields.
This process
continues for smaller and smaller fields as long as the current field has a
central cell and can be divided in the described manner.
For example, if n = 7 and m = 15, Farmer John will first place a cow in the cell with
coordinates (4, 8), after which he will divide the field into four subfields of
size 3 × 7. In each such subfield, he will place a cow in
the cell (2, 4) and then divide each of them into four subfields of size 1 × 3. This process
is illustrated below (cells containing cows are marked with the letter C):
A total of 21 cows
are required for such a field.
On the other
hand, if n = m = 5, Farmer John will place only one cow, since the resulting 2
× 2 subfields do not have central cells.
Help Farmer John
determine how many cows in total he will need to place on the field.
Input. Two integers n and m (1 ≤ n ≤ 109, 1
≤ m ≤ 109).
Output. Print the total
number of cows that will be placed on the field.
|
Sample input |
Sample output |
|
7 15 |
21 |
SOLUTION
recursion
Algorithm analysis
Farmer John
places cows strictly in the center of each field and recursively repeats the
process for the four equal subfields:
1.
A central cell exists if and only if both dimensions
of the field are odd.
2.
If at least one of the dimensions is even, the
process stops immediately.
3.
If a central cell exists, then:
·
exactly one cow is placed in it;
·
the field is divided into 4 identical rectangles;
·
the process is independently repeated for each of
them.
Let f(n, m)
be
the number of cows placed on a field of size n × m.
If at least one
of the numbers n or m is even, a central cell
does not exist. Therefore
f(n, m)
= 0
If both n and m are odd, place one cow in the center and then recursively place cows
in the four subfields of size n / 2
× m / 2:
f(n, m)
= 1 + 4 * f(n / 2, m / 2)
Example
Compute the
answer for the given test case.
f(7, 15)
= 1 + 4 * f(3, 7) = 1 + 4 * 5 = 21
f(3, 7) = 1 + 4 * f(1, 3) = 1 + 4 * 1 = 5
f(1, 3) = 1 + 4 * f(0, 1) = 1 + 4 * 0 = 1
Algorithm implementation
The function f returns the number of cows
that can be placed on a field of size n × m.
long long f(int n, int m)
{
if (n % 2 == 0 || m % 2 == 0) return 0;
return 1 + 4 * f(n / 2, m / 2);
}
The main part of the program. Read the input data.
scanf("%d %d", &n, &m);
Compute and print the answer.
res = f(n, m);
printf("%lld\n", res);
Java
implementation
import java.util.*;
public class Main
{
static long f(int n, int m)
{
if (n % 2 == 0 || m % 2 == 0) return 0;
return 1 + 4 * f(n/2, m/2);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m = con.nextInt();
long res = f(n, m);
System.out.println(res);
}
}
Python
implementation
The function f returns the number of cows
that can be placed on a field of size n × m.
def f(n, m):
if n % 2 == 0
or m % 2 == 0: return
0
return 1 + 4 * f(n // 2, m // 2)
The main part of the program. Read the input data.
n, m = map(int,input().split())
Compute and print the answer.
res = f(n, m);
print(res)